BZOJ1068【SCOI2007】压缩 <区间DP>

Problem

【SCOI2007】压缩

Description

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母与，其中标记重复串的开始，重复从上一个（如果当前位置左边没有，则从串的开始算起）开始的解压结果（称为缓冲串）。可以压缩为，下面是解压缩的过程：

另一个例子是可以被压缩为。

Input

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为。

Output

输出仅一行，即压缩后字符串的最短长度。

Sample Input

Input #1

aaaaaaa

Input #2

1	bcdcdcdcdxcdcdcdcd

Sample Output

Output #1

Output #2

HINT

样例解释
在第一个样例中，解为，在第二个例子中，解为。
数据规模
的数据满足

标签：区间DP

Solution

每次压缩的是连续的一段，考虑区间。

设表示压缩字符串的字串的最短长度，其中压缩后的串串首自带一个于是就会有两种转移：

若，则

但这样是有锅的…压缩后串中间的会影响到后面的。
例如，显然为一种压缩，但其复制一遍形成的表示的不是原串。这是因为中间的会使后面的少复制一截。

于是我们调整状态定义，定义表示压缩后除了串首不再含有任何一个，表示压缩后除了串首还含有其他，这样前者是可以整体复制的，而后者不行。
那么首先有边界条件。
转移有三种：

，表示直接把后缀接上去
，其中，表示把前一半复制一遍
，表示分成两半随便拼，只不过拼了以后不能复制，因为中间有

直接记忆化即可，注意第三种情况要判左右边界。

Code

#include <bits/stdc++.h>
#define MAX_N 50
#define INF 0x3f3f3f3f
#define mid ((l+r)>>1)
using namespace std;
int n, f[MAX_N+5][MAX_N+5][2];	char s[MAX_N+5];
int DP(int l, int r, bool x) {
    int &ret = f[l][r][x];
    if (ret^INF) return ret;
    if (l == r && !x) return ret = 2;
    if (x) {
        for (int i = l; i < r; i++) {
            ret = min(ret, DP(l, i, 0)+DP(i+1, r, 0));
            if (l < i) ret = min(ret, DP(l, i, 0)+DP(i+1, r, 1));
            if (i+1 < r) ret = min(ret, DP(l, i, 1)+DP(i+1, r, 0));
            if (l < i && i+1 < r) ret = min(ret, DP(l, i, 1)+DP(i+1, r, 1));
        }
    } else {
        for (int i = l; i < r; i++)
            ret = min(ret, DP(l, i, 0)+r-i);
        bool flag = (r-l)%2 == 1;
        for (int i = l, j = mid+1; i <= mid; i++, j++)
            if (s[i]^s[j]) flag = false;
        if (flag) ret = min(ret, DP(l, mid, 0)+1);
    }
    return ret;
}
int main() {
    scanf("%s", s+1), n = (int)strlen(s+1);
    memset(f, INF, sizeof f), DP(1, n, 0), DP(1, n, 1);
    return printf("%d", min(f[1][n][0], f[1][n][1])-1), 0;
}